/**
 * @program: LeetCode
 * @description: LeetCode : 198. 打家劫舍
 * @author: WXY
 * @create: 2023-01-12 21:17
 * @Version 1.0
 **/
public class Num198_rob {
    public static int rob1(int[] arr) {
        int len = arr.length;
        if (len == 1) return arr[0];
        //dp[i]表示：考虑下标i号（包括i）以内的房屋，最多可以偷窃的金额为dp[i]。
        int[] dp = new int[len];
        //dp[i] 的考虑由当前房屋是偷还是不偷，，
        //如果偷的话，dp[i] = dp[i - 2] + arr[i],
        //如果不偷，  dp[i] = dp[i -1]
        dp[0] = arr[0];
        dp[1] = Math.max(arr[0], arr[1]);
        for (int i = 2; i < arr.length; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + arr[i]);
        }
        return dp[len - 1];
    }


    public static int rob(int[] arr) {
        int[] dp = new int[arr.length + 1];
        if (arr.length == 1) return arr[0];
        dp[0] = arr[0];
        dp[1] = Math.max(arr[0], arr[1]);
        for (int i = 2; i < arr.length; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + arr[i]);
        }
        return dp[arr.length - 1];
    }
    public static void main(String[] args) {
        int[] arr = {2, 7, 9, 3, 1};
        int rob = rob(arr);
        System.out.println(rob);
    }
}
